package a2BDrzewa;

import java.util.TreeSet;
import sun.security.krb5.internal.tools.Klist;

public class Wezel {

	private int maxElementow;
	Wezel parent;
	private TreeSet<Para> Klucze = new TreeSet<Wezel.Para>();

	public Wezel gdzieWstawic(int liczba) {
		return Klucze.ceiling(new Para(liczba, null)).dziecko;
	}

	public int ceiling(int liczba) {
		return Klucze.ceiling(new Para(liczba, null)).klucz;
	}

	private void wstawPare(int wartosc, Wezel dziecko) {
		wstawPareINormalizuj(new Para(wartosc, dziecko));
	}

	class Para implements Comparable<Para> {

		Integer klucz;
		Wezel dziecko;

		public Para(Integer klucz, Wezel wskaznik) {
			this.klucz = klucz;
			this.dziecko = wskaznik;
		}

		@Override
		public int compareTo(Para o) {
			if (o == null) {
				throw new NullPointerException();
			}
			return klucz.compareTo(o.klucz);

		}

		@Override
		public String toString() {
			return klucz.toString();
		}
	}

	public Wezel(int maxEl, Wezel par) {
		maxElementow = maxEl;
		parent = par;

	}

	int size() {
		if (Klucze.isEmpty()) {
			return 0;
		}
		return (Klucze.size() - 1);
	}

	protected Wezel wstawPareINormalizuj(Para P) {
		Klucze.add(P);
		if (P.dziecko != null) {
			P.dziecko.parent = this;
		}
		if (this.size() > 2 * maxElementow) {
			Wezel mniejsze = new Wezel(maxElementow, null);
			while (this.size() > maxElementow + 1) {
				mniejsze.wstawPareINormalizuj(Klucze.pollFirst());
			}
			Para doGory = Klucze.pollFirst();
			mniejsze.wstawPare(Integer.MAX_VALUE, doGory.dziecko);
			doGory.dziecko = mniejsze;

			if (parent == null) {
				mniejsze.parent = parent = new Wezel(maxElementow, null);
				parent.wstawPareINormalizuj(doGory);
				parent.wstawPare(Integer.MAX_VALUE, this);
				return parent;
			}

			return parent.wstawPareINormalizuj(doGory);
		}
		return null;

	}

	public Wezel wstawLiczbe(int liczba) {
		if (this.size() == 0) {
			wstawPareINormalizuj(new Wezel.Para(Integer.MAX_VALUE, new Wezel(maxElementow, this)));
		}
		return wstawPareINormalizuj(new Wezel.Para(liczba, new Wezel(maxElementow, this)));

	}

	@Override
	public String toString() {
		return Klucze.toString();
	}

	void wypiszWezel(int liczba) {
		wypiszZTabem(liczba, 0);
	}

	void wypiszZTabem(int liczba, int wciecie) {
		if (liczba > 0) {
			for (int i = 1; i < wciecie; ++i) {
				System.out.print("|  ");
			}
			if (wciecie > 0) {
				System.out.print("|- ");
			}
			if (size() != 0) {
				for (Para p : Klucze) {
					if (p.klucz < Integer.MAX_VALUE) {
						System.out.print(p.klucz + " ");
					}
				}
			} else {
				System.out.print("pusty");
			}
			System.out.println("");
			for (Para p : Klucze) {
				p.dziecko.wypiszZTabem(liczba - 1, wciecie + 1);
			}
		}
	}

	void usun(int liczba) {

		Para usuwany = Klucze.ceiling(new Para(liczba, null)), podstawiany;
		while (usuwany.dziecko.size() != 0) {
			podstawiany = usuwany.dziecko.Klucze.lower(new Para(Integer.MAX_VALUE, null));
			usuwany.klucz = podstawiany.klucz;
			usuwany = podstawiany;
		}
		Wezel wezel = usuwany.dziecko.parent;
		wezel.Klucze.remove(usuwany);
		if (wezel.size() == 0) {
			wezel.Klucze.clear();
			//Wezel =usuwany.dziecko.parent.parent;
		}
		int rozmiarMnie = wezel.size();

		int rozmiarMniejszych = -1;
		int rozmiarWiekszych = -1;
		int rozmiarRodzica = -1;
		Wezel wezelParent = null, wezelMniejszy = null, wezelWiekszy = null;
		try {
			wezelMniejszy = wezel.parent.Klucze.lower(usuwany).dziecko;
			rozmiarMniejszych = wezelMniejszy.size();

		} catch (NullPointerException e) {
		}
		try {
			wezelWiekszy = wezel.parent.Klucze.higher(usuwany).dziecko;
			rozmiarWiekszych = wezelWiekszy.size();
		} catch (NullPointerException e) {
		}
		try {
			wezelParent = wezel.parent;
			rozmiarRodzica = wezelParent.size();
		} catch (NullPointerException e) {
		}
		//if(rozmiarMnie+rozmiarMniejszych+rozmiarRodzica<=2*maxElementow){
		if (rozmiarMnie < maxElementow && rozmiarMniejszych > maxElementow) {

			wezel.wstawPare(usuwany.klucz, wezelMniejszy.Klucze.pollLast().dziecko);
			wezelParent.Klucze.lower(usuwany).klucz = wezelMniejszy.Klucze.last().klucz;
			wezelMniejszy.Klucze.last().klucz = Integer.MAX_VALUE;
		}
		if (rozmiarMnie < maxElementow && rozmiarWiekszych > maxElementow) {

			wezel.Klucze.last().klucz=wezelParent.Klucze.higher(usuwany).klucz;
			wezelParent.Klucze.higher(usuwany).klucz=wezelWiekszy.Klucze.first().klucz;
			wezel.wstawPare(Integer.MAX_VALUE, wezelWiekszy.Klucze.pollFirst().dziecko);
							}
	}
}
